A data processor requires a variety of shift operations to implement its instruction set. These shift operations include left shifts, right shifts, and rotates. The rotate shifts the bit positions in the indicated direction but instead of causing the bits to "roll off" the end, the rotate wraps the bits around and shifts them into vacated bit positions at the other end. Left and right shifts can be arithmetic or logical, a characteristic which determines how bits at either end of the operand are handled. Each shift operation has a variable length. Which bit is shifted into a given bit position is determined by the type of shift operation. During the left or right shift, bits roll off the end and vacated bit positions must be filled with something. For example, the vacated bit positions may be filled with zero, one, the carry bit, or the sign bit, depending on the instruction type. A fill using the sign bit or the carry bit is called data-dependent because the value with which to fill the vacated bit positions cannot be determined ahead of time.
Several types of shifters are known in the art. A simple shift register stores an input operand in parallel, and then shifts the operand serially by one bit position for each clock cycle. When the operand has been shifted by the desired number of bits, the result is read out of the shift register in parallel. While the shift register requires only a small amount of integrated circuit area, a shift operation using a shift register requires multiple clock cycles and is generally not useful for high-speed data processing.
A second type of shifter, taught by Chas F. Studor and Robert Skruhak in U.S. Pat. No. 5,099,445, shifts the input operand by either one or a predetermined number of bit positions. Using this type of shifter, a long shift can be accomplished in a fewer number of clock cycles than for the shift register. While this shifter is much faster than the shift register, it requires more integrated circuit area to selectively connect each bit to both adjacent bits and to bits separated by the predetermined number of bit positions.
A third type of shifter which is yet faster is a barrel shifter. The barrel shifter includes connections from each bit of a source operand to each bit of a destination operand. Thus, the barrel shifter can perform a shift instruction by any arbitrary number of bit positions within a single clock cycle. Barrel shifters conventionally include two registers each of which function as either the source register or the destination register of the shift operation, depending on the direction. The source and destination registers are coupled to a shifter array, which is essentially an M-by-M matrix of transistors, where M is the operand size. For example, a 66-by-66 bit barrel shifter is taught by Ashok Someshwar and Bernard Pappert in U.S. Pat. No. 4,827,441, entitled "Barrel Shifter".
However, barrel shifters must sacrifice additional integrated circuit area and additional power consumption for the improved speed because of the large number of interconnections required. In addition, known barrel shifters require an additional clock cycle and additional hardware to perform data-dependent fills. What is needed is a barrel shifter architecture with reduced integrated circuit area which performs data-dependent fills more quickly.